When compositing images, there are cases where information called an alpha value indicating the overlay area and the degree of transparency of an object is appended in addition to the luminance of the object. The alpha value is determined for each pixel, an alpha value of 1 indicating complete opacity or occlusion and an alpha value of 0 complete transparency or nonocclusion. Alpha values become necessary when overlaying an image of an object onto a background image. Hereinafter, an image represented only by such alpha values is called an alpha plane.
In the case of a cloud, frosted glass, etc., an alpha value intermediate between [0, 1] may be used to represent the image, but there are cases where two values {0, 1} are sufficient.
For the encoding of a conventional binary alpha plane, binary image coding techniques such as MR and MMR, defined in CCITT""s international standards traditionally used for facsimile systems, etc., or coding techniques standardized by JBIG can be used. These coding schemes are referred to generically as binary still image coding. In binary still image coding, efficient coding can be achieved by predicting a low order pixel from a high order pixel in the scanning direction and by entropy-encoding the difference between them.
In a binary moving image, such as two successive alpha planes of a moving image, correlation between successive frames can be utilized. That is, efficient coding can be achieved by predicting a pixel to be encoded, from a previously obtained binary image having high correlation, and by encoding the difference between them, rather than predicting a low-order pixel from a high-order pixel in the scanning direction and encoding the difference between them.
However, binary still image coding in the prior art has exploited only the correlation between the high-order and low-order pixels in the scanning direction even when a binary image having high correlation with the binary image to be encoded or decoded is obtained at the encoder or decoder, and hence the prior art has had the problem that a large number of code bits are required.
For the encoding of a conventional alpha plane, waveform coding is used, as is done in the JPEG coding scheme.
However, many alpha planes have the property that most portions are uniform and intermediate values are distributed along the boundary.
Since such alpha planes contain high frequency components along the boundary, the waveform coding as employed in the prior art has had the problem that efficient coding is difficult to achieve.
In view of the above-described problems of the prior art, it is an object of the present invention to provide an image encoding apparatus, an image decoding apparatus, an image encoding method, an image decoding method, and a medium having recorded thereon a program which causes a computer to carry out their processing operations, wherein a pixel to be encoded is predicted from a previously obtained binary image having high correlation, and the difference between them is encoded, thereby achieving more efficient encoding and decoding than can be achieved with the binary image encoding and decoding techniques used in the prior art.
In view of the above-described problems, it is also an object of the present invention to provide an image encoding apparatus and its corresponding decoding apparatus, an image encoding method and its corresponding decoding method, and media storing their execution programs, wherein the distribution of intermediate values is analyzed, and a smoothing function approximating the distribution and a binary base image having only two values, a maximum value and a minimum value, are encoded respectively, thereby achieving more efficient coding than the prior art.
The present invention is an image encoding apparatus comprising: blocking means 1 for taking as an input a target binary image to be encoded, and for obtaining a target block by dividing said target binary image into blocks each containing a plurality of pixels; blocking means 2 for obtaining a reference block by dividing a previously obtained reference binary image into blocks each containing a plurality of pixels;
exclusive OR block constructing means for constructing an exclusive OR block by sequentially scanning said target block and said reference block and by exclusive-ORing pixel values between said two blocks; and exclusive OR encoding means for generating a coded sequence representative of the results of said exclusive-ORing, and for outputting the same as encoded data.
Another invention is an image decoding apparatus comprising: blocking means 2 for obtaining a reference block by dividing a previously obtained reference binary image into blocks each containing a plurality of pixels; exclusive OR decoding means for recovering said exclusive OR block by decoding the encoded data encoded by the image encoding apparatus one embodiment; and target block constructing means for constructing a target block by combining said exclusive OR block with said reference block.
Still another invention is an image encoding apparatus comprising: blocking means 1 for taking as an input a target binary image to be encoded, and for obtaining a target block by dividing said target binary image into blocks each containing a plurality of pixels; blocking means 2 for obtaining a reference block by dividing a previously obtained reference binary image into blocks each containing a plurality of pixels;
statistical model selecting means for selecting a statistical model from among a plurality of statistical models, based on the states of pixels surrounding a reference pixel in said reference block, said reference pixel corresponding to a target pixel in said target block; and entropy encoding means for entropy-encoding said target pixel based on said selected statistical model, and for outputting the same as encoded data.
Still another invention is an image decoding apparatus comprising: blocking means 2 for obtaining a reference block by dividing a previously obtained reference binary image into blocks each containing a plurality of pixels; statistical model selecting means for selecting a statistical model from among a plurality of statistical models, based on the states of pixels surrounding a reference pixel in said reference block, said reference pixel corresponding to a target pixel in said target block; and entropy decoding means for recovering said target block by entropy-decoding, based on said selected statistical model, the encoded data output from the image encoding apparatus of one embodiment.
Still another invention is an image encoding apparatus according to one embodiment, further comprising: motion estimating means for searching through said reference binary image for a block that most resembles said target block, and for obtaining motion information from the result of said searching, and wherein: said blocking means 2 is a motion compensated blocking means 2 which obtains a reference block by applying motion compensation to said reference binary image using said motion information, and said motion information also is output from said image encoding apparatus.
Still another invention is an image decoding apparatus according to one embodiment, wherein said blocking means 2 is a motion compensated blocking means 2 which obtains a reference block by applying motion compensation to said previously obtained reference binary image using the motion information output from the image encoding apparatus of another embodiment.
The present invention of claim 16 is an image encoding apparatus according to claim 9, further comprising: reference block adoption determining means for comparing said target block with said reference block, and for determining, based on the result of said comparison, whether said reference block is to be adopted or not, and thereby switching the remainder of processing between various means; and target pixel encoding means for generating a coded sequence representative of pixel values in said target block, and for outputting the same as encoded data, and wherein: when said reference block adoption determining means determines that said reference block is to be adopted, said entropy encoding means and said statistical model selecting means are operated so that said encoded data from said entropy encoding means is output, while on the other hand, when it is determined that said reference block is not to be adopted, said target pixel encoding means is operated so that said encoded data from said target pixel encoding means is output, and the result of the determination as to whether said reference block is to be adopted or not is output as a reference block adoption determining signal.
Still another invention is an image decoding apparatus according to one embodiment, further comprising: reference block adoption control means for determining, based on the reference block adoption determining signal output from the image encoding apparatus of another embodiment, whether said reference block is to be adopted or not, and thereby switching the remainder of processing between various means; and target pixel decoding means for recovering said target block by decoding said encoded data output from said image encoding apparatus, and wherein: when said reference block adoption control means determines that said reference block is to be adopted, said entropy decoding means and said statistical model selecting means are operated so that said target block from said entropy decoding means is output, while on the other hand, when it is determined that said reference block is not to be adopted, said target pixel decoding means is operated so that said target block from said target pixel decoding means is output.
Still another invention is an image encoding apparatus comprising: blocking means 1 for taking as an input a target binary image to be encoded, and for obtaining a target block by dividing said target binary image into blocks each containing a plurality of pixels; blocking means 2 for obtaining a reference block by dividing a previously obtained reference binary image into blocks each containing a plurality of pixels; statistical model generating means for generating a statistical model for a target pixel from said reference block; and entropy encoding means for entropy-encoding said target pixel based on said generated statistical model, and for outputting the same as encoded data.
Still another invention is an image decoding apparatus comprising: blocking means 2 for obtaining a reference block by dividing a previously obtained reference binary image into blocks each containing a plurality of pixels; statistical model generating means for generating a statistical model for a target pixel from said reference block; and entropy decoding means for recovering said target block by entropy-decoding, based on said generated statistical model, the encoded data output from the image encoding apparatus of one embodiment.
Still another invention is an image encoding method comprising the steps of: taking as an input a target binary image to be encoded, and obtaining a target block by dividing said target binary image into blocks each containing a plurality of pixels; obtaining a reference block by dividing a previously obtained reference binary image into blocks each containing a plurality of pixels; constructing an exclusive OR block by sequentially scanning said target block and said reference block and by exclusive-ORing pixel values between said two blocks; and generating a coded sequence representative of the results of said exclusive-ORing, and outputting the same as encoded data.
Still another invention is an image decoding method comprising the steps of: obtaining a reference block by dividing a previously obtained reference binary image into blocks each containing a plurality of pixels; taking the encoded data encoded by the image encoding method of claim 26 as an input, and recovering said exclusive OR block by decoding said encoded data; and constructing a target block by combining said exclusive OR block with said reference block.
Still another invention is an image encoding method comprising: blocking step 1 for taking as an input a target binary image to be encoded, and for obtaining a target block by dividing said target binary image into blocks each containing a plurality of pixels; blocking step 2 for obtaining a reference block by dividing a previously obtained reference binary image into blocks each containing a plurality of pixels; statistical model selecting step for selecting a statistical model from among a-plurality of statistical models, based on the states of pixels surrounding a reference pixel in said reference block, said reference pixel corresponding to a target pixel in said target block; and entropy encoding step for entropy-encoding said target pixel based on said selected statistical model, and for outputting the same as encoded data.
Still another invention is an image decoding method comprising: blocking step 2 for obtaining a reference block by dividing a previously obtained reference binary image into blocks each containing a plurality of pixels; statistical model selecting step for selecting a statistical model from among a plurality of statistical models, based on the states of pixels surrounding a reference pixel in said reference block, said reference pixel corresponding to a target pixel in said target block; and entropy decoding step for recovering said target block by entropy-decoding, based on said selected statistical model, the encoded data output in accordance with the image encoding method of one embodiment.
Still another invention is an image encoding method according to one embodiment, further comprising: motion estimating step for searching through said reference binary image for a block that most resembles said target block, and for obtaining motion information from the result of said searching, and wherein: said blocking step 2 is a motion compensated blocking step 2 which obtains a reference block by applying motion compensation to said reference binary image using said motion information, and said motion information also is output from said image encoding method.
Still another invention is an image decoding method according to one embodiment, wherein said blocking step 2 is a motion compensated blocking step 2 which obtains a reference block by applying motion compensation to said previously obtained reference binary image using the motion information output in accordance with the image encoding method of one embodiment.
Still another invention is an image encoding method according to one embodiment, further comprising: reference block adoption determining step for comparing said target block with said reference block, and for determining, based on the result of said comparison, whether said reference block is to be adopted or not, and thereby switching the execution of subsequent steps; and target pixel encoding step for generating a coded sequence representative of pixel values in said target block, and for outputting the same as encoded data, and wherein: when it is determined in said reference block adoption determining step that said reference block is to be adopted, said entropy encoding step and said statistical model selecting step are executed so that said encoded data from said entropy encoding step is output, while on the other hand, when it is determined that said reference block is not to be adopted, said target pixel encoding step is executed so that said encoded data from said target pixel encoding step is output, and the result of the determination as to whether said reference block is to be adopted or not is output as a reference block adoption determining signal.
Still another invention is an image decoding method according to one embodiment, further comprising: reference block adoption control step for determining, based on the reference block adoption determining signal output in accordance with the image encoding method of another embodiment, whether said reference block is to be adopted or not, and thereby switching the execution of subsequent steps; and target pixel decoding step for recovering said target block by decoding said encoded data output in accordance with said image encoding method, and wherein: when it is determined in said reference block adoption control step that said reference block is to be adopted, said entropy decoding step and said statistical model selecting step are executed so that said target block from said entropy decoding step is output, while on the other hand, when it is determined that said reference block is not to be adopted, said target pixel decoding step is executed so that said target block from said target pixel decoding step is output.
Still another invention is an image encoding method comprising the steps of: taking as an input a target binary image to be encoded, and obtaining a target block by dividing said target binary image into blocks each containing a plurality of pixels; obtaining a reference block by dividing a previously obtained reference binary image into blocks each containing a plurality of pixels; generating a statistical model for a target pixel from said reference block; and entropy-encoding said target pixel based on said generated statistical model, and outputting the same as encoded data.
Still another invention is an image decoding method comprising: obtaining a reference block by dividing a previously obtained reference binary image into blocks each containing a plurality of pixels; generating a statistical model for a target pixel from said reference block; and recovering said target block by entropy-decoding, based on said generated statistical model, the encoded data output in accordance with the image encoding method of one embodiment.
Still another invention is an image encoding apparatus comprising: multi-value to binary converting means for taking a target multi-value image to be encoded and a smoothing function as inputs, and for generating a binary image from said multi-value image on the basis of said smoothing function; binary image encoding means for encoding said binary image, and for outputting the same as binary image encoded data; and smoothing function encoding means for encoding said smoothing function, and for outputting the same as smoothing function encoded data, and wherein: said smoothing function is a function so adjusted that the original multi-value image could, in effect, be reproduced if said smoothing function were applied to said binary image.
Still another invention is an image encoding apparatus comprising: smoothing function estimating means for estimating a smoothing function from a target multi-value image to be encoded; multi-value to binary converting means for converting said multi-value image to a binary image based on a multi-value to binary conversion criterion determined to match said estimated smoothing function; binary image encoding means for encoding said binary image, and for outputting the same as binary image encoded data; and smoothing function encoding means for encoding said estimated smoothing function, and for outputting the same as smoothing function encoded data.
Still another invention is an image encoding apparatus comprising: multi-value to binary converting means for generating a binary image from a target multi-value image to be encoded; binary image encoding means for encoding said binary image, and for outputting the same as binary image encoded data; smoothing function generating means for generating a smoothing function from said binary image and said target multi-value image; and smoothing function encoding means for encoding said smoothing function, and for outputting the same as smoothing function encoded data.
Still another invention is an image encoding apparatus according to one embodiment, wherein said smoothing function is expressed using one or more tables consisting of binarization patterns of neighboring pixels and substitution values corresponding to said patterns.
Still another invention is an image encoding apparatus according to one embodiment, further comprising:
binary to multi-value converting means for generating a multi-value image by smoothing said binary image using said smoothing function; and residual component encoding means for encoding a residual component existing between the multi-value image generated by said binary to multi-value converting means and said target multi-value image input for conversion by said multi-value to binary converting means.
Still another invention is an image encoding apparatus comprising: multi-value to binary converting means for converting a multi-value image, which is a target image to be encoded, to a binary image based on a multi-value to binary conversion criterion determined to match said multi-value image; smoothing function estimating means for estimating a smoothing function such that the original multi-value image could, in effect, be reproduced if said smoothing function were applied to said binary image; binary image encoding means for encoding said binary image, and for outputting the same as binary image encoded data; and smoothing function encoding means for encoding said estimated smoothing function, and for outputting the same as smoothing function encoded data.
Still another invention is an image decoding apparatus comprising: means for receiving as inputs thereto the various encoded data encoded by the image encoding apparatus of one embodiment; binary image decoding means for recovering said binary image by decoding said binary image encoded data out of said encoded data; smoothing function decoding means for recovering said smoothing function by decoding said smoothing function encoded data out of said encoded data; and binary to multi-value converting means for recovering said multi-value image by smoothing said decoded binary image using said decoded smoothing function.
Still another invention is an image decoding apparatus comprising: means for receiving as inputs thereto the various encoded data encoded by the image encoding apparatus of one embodiment; binary image decoding means for recovering said binary image by decoding said binary image encoded data out of said encoded data; smoothing function decoding means for recovering said smoothing function by decoding said smoothing function encoded data out of said encoded data; dynamic range decoding means for recovering said dynamic range by decoding said dynamic range encoded data out of said encoded data; and binary to multi-value converting means for recovering said multi-value image by smoothing said decoded binary image using said decoded smoothing function and by converting pixel values using said decoded dynamic range.
Still another invention is an image decoding apparatus comprising: means for receiving as inputs thereto the various encoded data encoded by the image encoding apparatus of one embodiment; binary image decoding means for recovering said binary image by decoding said binary image encoded data out of said encoded data; smoothing function decoding means for recovering said smoothing function by decoding said smoothing function encoded data out of said encoded data; and binary to multi-value converting means for recovering said multi-value image by smoothing said decoded binary image using said decoded smoothing function, and wherein: said decoded smoothing function is expressed using one or more tables consisting of binarization patterns of neighboring pixels and substitution values corresponding to said patterns.
Still another invention is an image decoding apparatus comprising: means for receiving as inputs thereto the various encoded data encoded by the image encoding apparatus of one embodiment; binary image decoding means for recovering said binary image by decoding said binary image encoded data out of said encoded data; smoothing function decoding means for recovering said smoothing function by decoding said smoothing function encoded data out of said encoded data; binary to multi-value converting means for recovering said multi-value image by smoothing said decoded binary image using said decoded smoothing function; and residual component decoding means for decoding said residual component, and wherein: an output image is obtained by adding said decoded residual component to the output from said binary to multi-value converting means.